package com.wp.InterviewAlgorithm.lesson1;

/**
 * Created by 王萍 on 2017/9/18 0018.
 */

import com.wp.utils.LinkedListUtil;
import com.wp.utils.LinkedListUtil.Node;

/**
 * 给定一个链表和一个值x，将链表划分为两部分，是的划分后小于x的结点在前，大于x的结点在后
 * 在这两部分中要保持原链表中的出现顺序。
 * 如：1->4->3->2->5->2和x=3，返回 1->2->2->4->3->5
 */
public class 链表划分 {
    public static void main(String[] args) {

        Node node = LinkedListUtil.produceList(6);
        LinkedListUtil.printNode(node);
        Node divideList = divideList(node, 5);
        LinkedListUtil.printNode(divideList);
    }

    private static Node divideList(Node node,int x) {
        Node left=new Node(0),right=new Node(0);
        Node pLeft=left,pRight=right;
        while (node!=null){
            if (node.value<x){
                pLeft.next=new Node(node.value);
                pLeft=pLeft.next;
            }else {
                pRight.next=new Node(node.value);
                pRight=pRight.next;
            }
            node=node.next;
        }
        pLeft.next=right.next;
        node=left.next;
        return node;
    }
}
